package msb.class09;


import org.junit.Assert;

import java.util.ArrayList;

/**
 * 快慢指针
 * 慢指针走1步
 * 快指针走2步
 */
public class Code01_LinkedListMid {
    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidNode(Node head) {
        //一个都没有
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;

        while (true) {
            if (fast.next == null || fast.next.next == null) {
                return slow;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     *
     * @param head
     * @return
     */
    public static Node midOrDownMidNode(Node head) {
        //一个都没有
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;

        while (true) {
            if (fast.next == null) {
                return slow;
            }
            if (fast.next.next == null) {
                return slow.next;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidPreNode(Node head) {
        //一个都没有
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;
        Node pre = null;

        while (true) {
            if (fast.next == null || fast.next.next == null) {
                return pre;
            }
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     *
     * @param head
     * @return
     */
    public static Node midOrDownMidPreNode(Node head) {
        //一个都没有
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;
        Node pre = null;

        while (true) {
            if (fast.next == null) {
                return pre;
            }
            if (fast.next.next == null) {
                return slow;
            }
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
    }


    public static Node right1(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 1) / 2);
    }

    public static Node right2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }

    public static Node right3(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 3) / 2);
    }

    public static Node right4(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 2) / 2);
    }

    public static void main(String[] args) {

        for (int i = 1; i < 10; i++) {
            Node head = new Node(0);
            Node test = head;
            for (int j = 1; j <= i; j++) {
                test.next = new Node(j);
                test = test.next;
            }
            printLinkedList(head);

            Node ans1 = null;
            Node ans2 = null;

//            ans1 = midOrUpMidNode(head);
//            ans2 = right1(head);

//            ans1 = midOrDownMidNode(head);
//            ans2 = right2(head);

//            ans1 = midOrUpMidPreNode(head);
//            ans2 = right3(head);


            ans1 = midOrDownMidPreNode(head);
            ans2 = right4(head);

            System.out.println(ans1 != null ? ans1.value : "无");
            System.out.println(ans2 != null ? ans2.value : "无");
            Assert.assertSame(ans1, ans2);
        }
    }

    public static void printLinkedList(Node head) {
        while (head != null) {
            System.out.print(head.value + "-");
            head = head.next;
        }
        System.out.println();
    }
}
